package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/insert-into-a-sorted-circular-linked-list'>循环有序列表的插入(Insert into a Sorted Circular Linked List)</a>
 * <p>给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环非降序的。</p>
 * <p>给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。</p>
 * <p>如果有多个满足条件的插入位置，你可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。</p>
 * <p>如果列表为空（给定的节点是 null），你需要创建一个循环有序列表并返回这个节点。否则，请返回原先给定的节点。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：head = [3,4,1], insertVal = 2
 *      输出：[3,4,1,2]
 *      解释：有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。
 *
 *  示例 2：
 *      输入：head = [], insertVal = 1
 *      输出：[1]
 *      解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。
 *
 *  示例 3：
 *      输入：head = [1], insertVal = 0
 *      输出：[1,0]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>0 <= Number of Nodes <= 5 * 10^4</li>
 *     <li>-10^6 <= Node.val, insertVal <= 10^6</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/13 9:18
 */
public class LC0708InsertIntoSortedCircularLinkedList_M {
    static class Solution {
        public Node insert(Node head, int insertVal) {
            Node newNode = new Node(insertVal);
            // 1.当链表为空时，新建节点并让next指向自身，返回。
            if (head == null) {
                newNode.next = newNode;
                return newNode;
            }
            /*
                2.当链表不为空时
                    ==> 如果能够找到a <= insertVal <= b，那么将insertVal生成的node插入到aNode的后面，bNode的前面
                    ==> 如果没有找到这样的区间呢？说明insertVal大于或小于链表中所有节点的值，即插入值是最大值或最小值。
                此时：找出最大值的最后一个点，直接在该最大值的点的后面插入结点即可
            */
            // 找到具有最大值的节点，即为maxNode，下一个节点就是具有最小值的节点，即为minNode
            Node maxNode = head;
            while (maxNode.next != head && maxNode.val <= maxNode.next.val) {
                maxNode = maxNode.next;
            }
            Node minNode = maxNode.next;
            // 如果insertVal比maxNode.val大 或者 比minNode.val小
            if (insertVal < minNode.val || insertVal > maxNode.val) {
                newNode.next = minNode;
                maxNode.next = newNode;
            } else {
                // 找到currNode.val<= insertVal && currNode.next.val>= insertVal 的位置
                Node currNode = minNode;
                while (currNode.next.val < insertVal) {
                    currNode = currNode.next;
                }
                newNode.next = currNode.next;
                currNode.next = newNode;
            }
            return head;
        }
    }

    static class Node {
        public int val;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }

    public static void main(String[] args) {
        Node node = new Node(3);
        node.next = new Node(4);
        node.next.next = new Node(1);
        node.next.next.next = node;

        Solution solution = new Solution();
        Node insert = solution.insert(node, 2);
        Node curr = insert;
        System.out.println(curr.val);
        curr = curr.next;
        while (curr != null && curr != insert) {
            System.out.println(curr.val);
            curr = curr.next;
        }

    }
}
